package zhuzx.solution;

public class ZingFrontAnswer {
	
	public static void main(String[] args) {
		testIsSuper();
//		testFindWord();
	}
	
	public static void testIsSuper() {
		String A = "abbccdd";
		String B = "abcdd";
		System.out.println(isSuper(A, B) + "\n");
		A = "abbccd";
		B = "abcdd";
		System.out.println(isSuper(A, B));
	}
	
	/**
	 * 简单的解法：使用两个HashMap分别统计两个字符串，再迭代smallSet的Map，逐一与largeSet的Map中的对应值相比较。
	 * 本方法实现速度最优解：以字符的unicode值为数组下标，出现次数为数组元素，可以用最快的速度统计完毕。
	 * 不妥之处在于，对于需要用两个代码单元表示的特殊字符，本方法将返回错误的结果。
	 * 所以遇到该特殊场合，需要构建更大的数组并使用codePointAt获取字符（但速度远比charAt慢）。
	 */
	public static boolean isSuper(String largeSet, String smallSet) {
		//省略判断非空代码。。。
		if (largeSet.length() < smallSet.length()) return false;
		//以字符的unicode值为索引，出现的次数为值，65536是unicode码值的范围。
		int[] large = new int[65536];
		int[] small = new int[65536];
		for (int i=0; i<largeSet.length(); i++) {
			int key = largeSet.charAt(i);
			large[key] = large[key] + 1;
		}
		for (int i=0; i<smallSet.length(); i++) {
			int key = smallSet.charAt(i);
			small[key] = small[key] + 1;
			//不满足
			if (large[key]==0 || large[key]<small[key]) {
				System.out.println((char) key + "不满足，largeSet出现" + large[key] + "次，"
						+ "smallSet出现" + small[key] + "次");
				return false;
			}
		}
		return true;
	}
	
	public static void testFindWord() {
		char[][] boggle = {
				{'G','I','Z'},
				{'U','E','K'},
				{'Q','S','E'}
		};
		String[] dictionary = {"GEEKS", "FOR", "QUIZ", "GO", "EZQU"};
		findWord(boggle, dictionary);
	}
	
	/**
	 * 简单地逐步寻找匹配字符
	 * @param alphabet 字母表
	 * @param words 需要寻找的单词
	 */
	public static void findWord(char[][] alphabet, String[] words) {
		eachWord: for (String w : words) {
			Point start = null;
			seachHead: for (int i=0; i<alphabet.length; i++) {
				char[] row = alphabet[i];
				for (int j=0; j<row.length; j++) {
					if (row[j] == w.charAt(0)) {
						start = new Point(row[j], i, j);
						break seachHead;
					}
				}
			}
			if (start == null) {
				System.out.println("未找到头字符：" + w);
				continue;
			}
			Point cursor = start;
			System.out.println("开始匹配：" + w + "\n" + cursor);
			eachChar: for (int i=1; i<w.length(); i++) {
				Point[] available = getAvailableChars(alphabet, cursor.verIndex, cursor.horIndex);
				for (Point point : available) {
					if (point.value == w.charAt(i)) {
						cursor = point;
						System.out.println(cursor);
						continue eachChar;//找到字符，继续下一个字符。
					}
				}
				System.out.println("匹配中断：" + w);
				continue eachWord;//这个字符未寻获，该单词匹配失败。
			}
			System.out.println("已找齐：" + w);
		}
	}
	
	/**
	 * @param verIndex 垂直坐标，外层数组下标。
	 * @param horIndex 水平坐标，子数组下标
	 */
	private static Point[] getAvailableChars(char[][] alphabet, int verIndex, int horIndex) {
		int verLimit = alphabet.length - 1;
		int horLimit = alphabet[0].length - 1;
		Point[] points = new Point[8];
		int cursor = 0;
		for (int i=-1; i<=1; i++) {
			for (int j=-1; j<=1; j++) {
				if (i==0 && j==0) continue;
				int newVer = verIndex + i;
				int newHor = horIndex + j;
				if (newVer>=0 && newVer<=verLimit && newHor>=0 && newHor<=horLimit) {
					points[cursor] = new Point(alphabet[newVer][newHor], newVer, newHor);
					cursor++;
				}
			}
		}
		Point[] result = new Point[cursor];
		System.arraycopy(points, 0, result, 0, cursor);
		return result;
	}
	
	static class Point {
		char value;
		int verIndex;
		int horIndex;
		public Point(char value, int verIndex, int horIndex) {
			this.value = value;
			this.verIndex = verIndex;
			this.horIndex = horIndex;
		}
		public String toString() {
			return "Point [value=" + value + ", verIndex=" + verIndex
					+ ", horIndex=" + horIndex + "]";
		}
	}

}